/* 
   Copyright (c) 2008 - Chris Buckley. 

   Permission is granted for use and modification of this file for
   research, non-commercial purposes. 
*/

#include "common.h"
#include "sysfunc.h"
#include "trec_eval.h"
#include "functions.h"
#include "trec_format.h"
double log2(double x);

static int
te_calc_G(const EPI * epi, const REL_INFO * rel_info,
          const RESULTS * results, const TREC_MEAS * tm, TREC_EVAL * eval);
static PARAMS default_G_gains = { NULL, 0, NULL };

/* See trec_eval.h for definition of TREC_MEAS */
TREC_MEAS te_meas_G = { "G",
    "    Normalized Gain\n\
    Experimental measure 4/10/2008\n\
    G is a gain related measure that combines qualities of MAP and NDCG.\n\
    Contribution of doc doc retrieved at rank i is \n\
    G(doc) == gain (doc) / log2 (2+ideal_gain(i)-results_gain(i))\n\
    where results_gain(i) is sum gain(doc) for all docs before i\n\
    and ideal_gain is the maximum possible results_gain(i)\n\
    G is the sum of G(doc) over all docs, normalized by max ideal_gain.\n\
    Gain values are set to the appropriate relevance level by default.  \n\
    The default gain can be overridden on the command line by having \n\
    comma separated parameters 'rel_level=gain'.\n\
    Eg, 'trec_eval -m G.1=3.5,2=9.0,4=7.0 ...'\n\
    will give gains 3.5, 9.0, 3.0, 7.0 for relevance levels 1,2,3,4\n\
    respectively (level 3 remains at the default).\n\
    Gains are allowed to be 0 or negative, and relevance level 0\n\
    can be given a gain.\n\
    The idea behind G is that the contribution of a doc retrieved at i\n\
    should not be independent of the docs before. If most docs before have\n\
    higher gain, then the retrieval of this doc at i is nearly as good as \n\
    possible, and should be rewarded appropriately\n",
    te_init_meas_s_double_p_pair,
    te_calc_G,
    te_acc_meas_s,
    te_calc_avg_meas_s,
    te_print_single_meas_s_double,
    te_print_final_meas_s_double_p,
    &default_G_gains, -1
};

static int
te_calc_G(const EPI * epi, const REL_INFO * rel_info,
          const RESULTS * results, const TREC_MEAS * tm, TREC_EVAL * eval)
{
    RES_RELS res_rels;
    double results_gain, sum_results;
    double ideal_gain, sum_ideal;
    double sum_cost, min_cost;
    double results_g;
    long cur_level, num_at_level;
    long i;
    GAINS gains;

    if (UNDEF == te_form_res_rels(epi, rel_info, results, &res_rels))
        return (UNDEF);

    if (UNDEF == setup_gains(tm, &res_rels, &gains))
        return (UNDEF);

    results_g = 0.0;
    sum_results = 0.0;
    sum_ideal = 0.0;
    sum_cost = 0.0;
    cur_level = gains.num_gains - 1;
    ideal_gain = (cur_level >= 0) ? gains.rel_gains[cur_level].gain : 0.0;
    num_at_level = 0;
    min_cost = 1.0;

    for (i = 0; i < res_rels.num_ret && ideal_gain > 0.0; i++) {
        /* Calculate change in actual results */
        results_gain = get_gain(res_rels.results_rel_list[i], &gains);
        sum_results += results_gain;
        /* Calculate change in ideal results */
        num_at_level++;
        while (cur_level >= 0 &&
               num_at_level > gains.rel_gains[cur_level].num_at_level) {
            num_at_level = 1;
            cur_level--;
            ideal_gain =
                (cur_level >= 0) ? gains.rel_gains[cur_level].gain : 0.0;
        }
        if (ideal_gain > 0.0)
            sum_ideal += ideal_gain;
        if (ideal_gain >= min_cost)
            sum_cost += ideal_gain;
        else
            sum_cost += min_cost;

        /* Calculate G */
        if (results_gain != 0)
            results_g += results_gain /
                log2((double) (2 + sum_cost - sum_results));

        if (epi->debug_level > 0)
            printf("G: %ld %ld %3.1f %6.4f %3.1f %6.4f %6.4f %6.4f\n",
                   i, cur_level, results_gain, sum_results,
                   ideal_gain, sum_ideal, sum_cost, results_g);
    }
    while (i < res_rels.num_ret) {
        /* Calculate change in results gain */
        results_gain = get_gain(res_rels.results_rel_list[i], &gains);
        sum_results += results_gain;
        sum_cost += min_cost;
        if (results_gain != 0)
            results_g += results_gain /
                log2((double) (2 + sum_cost - sum_results));
        if (epi->debug_level > 0)
            printf("G: %ld %ld %3.1f %6.4f %3.1f %6.4f %6.4f\n",
                   i, cur_level, results_gain, sum_results, 0.0,
                   sum_ideal, results_g);
        i++;
    }
    while (ideal_gain > 0.0) {
        /* Calculate change in ideal results gain */
        num_at_level++;
        while (cur_level >= 0 &&
               num_at_level > gains.rel_gains[cur_level].num_at_level) {
            num_at_level = 1;
            cur_level--;
            ideal_gain =
                (cur_level >= 0) ? gains.rel_gains[cur_level].gain : 0.0;
        }
        if (ideal_gain > 0.0)
            sum_ideal += ideal_gain;
        if (epi->debug_level > 0)
            printf("G: %ld %ld %3.1f %6.4f %3.1f %6.4f\n",
                   i, cur_level, 0.0, sum_results, ideal_gain, sum_ideal);
        i++;
    }

    /* Compare sum to ideal G */
    if (sum_ideal > 0.0) {
        eval->values[tm->eval_index].value = results_g / sum_ideal;
    }

    Free(gains.rel_gains);
    return (1);
}
